/*******************************************************************************
 * Created on 2018年7月18日 上午9:08:16
 ******************************************************************************/
package org.yao.algorithm;

import java.util.Arrays;

/**
 * 选择排序
 * 每趟排序选择最小的一个元素顺序排列在已排好序的元素后，直到排序结束 
 * 时间复杂度：比较次数与序列的初始排序无关。设排序序列为n，比较次数永为n(n-1)/2。
 *          移动次数与初始排序有关。序列正序时，移动次数为0最少，反序时移动次数为3n(n-1)/2最多。
 * @since 1.0.0
 */
public class SelectSort {

    /**
     * @param arr 将排序数组
     * @param isDesc 是否降序
     *
     * @author 2018年7月18日 上午9:22:05
     */
    protected static void sort(int[] arr, boolean isDesc) {
        System.out.println("排序前");
        Arrays.stream(arr).forEach(item -> System.out.print(item+" "));
        
        //选择排序遍历第i趟排序
        for (int i = 0; i < arr.length; i++) {
            int k = i;
            //记录最小元素所在的位置
            for (int j = i; j < arr.length; j++) {
                if (isDesc) {
                    if (arr[j] > arr[k]) k = j;
                }else {
                    if (arr[j] < arr[k]) k = j;
                }
                
            }
            
            if (i != k) {
                //将最小元素与当前遍历数组的起始元素替换
                int temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }
        }

        System.out.println();
        System.out.println("排序后");
        Arrays.stream(arr).forEach(item -> System.out.print(item + " "));
    }
    
    
    
    public static void main(String[] args) {
        int[] arr = {1,3,2,45,65,33,12,12};
        sort(arr, false);
    }
}
